//
// Created by wenyaxi on 24-10-28.
//
#include <common.h>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> elementData;

    int k_range;
    int n_range;

    explicit Solution() {
    }

    int findKthLargest(vector<int> &nums, int k) {
        elementData = move(nums);
        this->n_range = k;
        this->k_range = (k - 1) / 2;
        heapify();
        for (int i = n_range; i < elementData.size(); i++) {
            if (elementData[i] > elementData[0]) {
                swap(elementData[i], elementData[0]);
                sink(0);
            }
        }
        return elementData[0];
    }

    void heapify() {
        for (int i = k_range; i >= 0; i--) {
            sink(i);
        }
    }

    void sink(int index) {
        int leftIndex = 2 * index + 1;
        int rightIndex = 2 * index + 2;
        if (rightIndex < n_range) {
            //两个子节点
            if (elementData[leftIndex] > elementData[rightIndex]) {
                if (elementData[rightIndex] < elementData[index]) {
                    swap(elementData[index], elementData[rightIndex]);
                    sink(rightIndex);
                }
            } else {
                if (elementData[leftIndex] < elementData[index]) {
                    swap(elementData[index], elementData[leftIndex]);
                    sink(leftIndex);
                }
            }
        } else if (leftIndex == n_range - 1) {
            //仅有左子节点
            if (elementData[index] > elementData[leftIndex]) {
                swap(elementData[index], elementData[leftIndex]);
            }
        }
    }
};

int main() {
    auto x = new Solution();
    /**
    *  [3,2,1,5,6,4]
        2
        [3,2,3,1,2,4,5,5,6]
        4
     *
     */
    vector<int> v = {3, 2, 1, 5, 6, 4};
    int find_kth_largest = x->findKthLargest(v, 2);
    cout<< find_kth_largest;
    return 0;
}
